package com.cjm.del;

import com.cjm.algorithm.GeneratorUtils;
import com.cjm.algorithm.HelpUtils;

public class Demo {
    private static int partition(int[] arr, int l, int r) {
        int flag = arr[l];
        int location = l;
        for(int i = l+1;i<=r;i++) {
            if (arr[i] < flag) {
                location++;
                HelpUtils.swap(arr, i, location);
            }
        }
        HelpUtils.swap(arr, l, location);
        return location;
    }

    /**
     * 这里我们要知道, 归并排序, 是从下到上的, 但是快速排序, 是从上到下的
     * 它会选择一个随机数, 来当作中间的一个数, 当走完层, 那么这个数的左边, 是小于这个数的
     * 这个数的右边, 是大于这个数的
     */
    private static void sort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }

    private static void sort(int[] arr) {
        int n = arr.length;
        sort(arr, 0, n - 1);
    }

    public static void main(String[] args) {
        for (int i = 0; i < 20; i++) {
            int[] generator = GeneratorUtils.generator(100000, 0, 100000);
            sort(generator);
            GeneratorUtils.print(generator);
        }
    }
}
